//
// Created by ASUS on 2024/11/22/星期五.
//
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 10;  // 可以根据数据范围调整大小
const int INF = 0x3f3f3f3f;

struct Node {
	int lson, rson;  // 左右子节点编号
	int val;  // 节点所维护的值，这里以区间和为例
} tree[MAXN * 40];  // 动态开点，所以开大点，根据实际情况调整

int tot = 0;  // 节点编号，从0开始计数
int root = 0;  // 线段树的根节点编号

// 动态开点建树，这里传入当前节点编号，区间左右端点
void build(int &now, int l, int r) {
	now = ++tot;  // 分配新节点编号
	if (l == r) {
		// 这里假设初始值都是0，可以根据实际输入情况修改
		tree[now].val = 0;
		return;
	}
	int mid = (l + r) >> 1;
	build(tree[now].lson, l, mid);
	build(tree[now].rson, mid + 1, r);
	tree[now].val = tree[tree[now].lson].val + tree[tree[now].rson].val;
}

// 单点修改，pos为要修改的位置，val为修改后的值，当前节点编号now，区间左右端点l和r
void update(int &now, int l, int r, int pos, int val) {
	if (!now) now = ++tot;  // 如果当前节点不存在，分配新节点
	if (l == r) {
		tree[now].val = val;
		return;
	}
	int mid = (l + r) >> 1;
	if (pos <= mid) {
		update(tree[now].lson, l, mid, pos, val);
	} else {
		update(tree[now].rson, mid + 1, r, pos, val);
	}
	tree[now].val = tree[tree[now].lson].val + tree[tree[now].rson].val;
}

// 区间查询，[ql, qr]为查询区间，当前节点编号now，线段树维护区间的左右端点l和r
int query(int now, int l, int r, int ql, int qr) {
	if (!now) return 0;  // 如果节点不存在，返回0
	if (ql <= l && r <= qr) return tree[now].val;
	int mid = (l + r) >> 1;
	int res = 0;
	if (ql <= mid) res += query(tree[now].lson, l, mid, ql, qr);
	if (qr > mid) res += query(tree[now].rson, mid + 1, r, ql, qr);
	return res;
}

int main() {
	build(root, 1, MAXN);  // 建树，初始区间[1, MAXN]

	// 示例操作
	// 单点修改
	update(root, 1, MAXN, 5, 10);  // 将位置5的值修改为10

	// 区间查询
	int result = query(root, 1, MAXN, 1, 10);
	cout << "区间[1, 10]的和为: " << result << endl;

	return 0;
}